Counter (CTR) mode takes a different approach to most other modes of operation. It does not even use the block cipher's encryption function
The encryption process begins by dividing the message into blocks
The final ciphertext is obtained by concatenating all ciphertext blocks and prepending them with the initialisation vector, which is necessary for decryption just as with CBC mode.
This process essentially turns a block cipher into a stream cipher where the IV and the counter are used to generate a keystream which is then XOR-ed with the message.
The decryption procedure is almost equivalent - the IV is extracted from the ciphertext
That's right - the decryption function
So long as the initialisation vector is chosen uniformly at random and the block cipher used is secure, i.e. it uses a pseudorandom function (or permutation) for its
First suppose, towards contradiction, that there is an efficient adversary Eve that after querying $\textit{Enc}_k$ with $q$ messages $m_1, m_2, ..., m_q$ and obtaining their ciphertexts $c_1, c_2, ..., c_q$, can distinguish with probability $\frac{1}{2} + \textit{nonnegl}(n)$ if a ciphertext $c$ is the encryption of $m_a$ or $m_b$, for some messages $m_a$ and $m_b$, which are also allowed to be one of the previously queried messages.
Consider the case where the messages $m_a$ and $m_b$ are only a single block long. If instead of the PRF $\textit{Enc}_k$, the CTR encryption used a truly random function $R$, then Eve would lack any information and so she would only be able guess at best with probability $\frac{1}{2}$ whether a ciphertext $c$ belongs to $m_a$ or $m_b$. This, however, is a contradiction because she would be able to distinguish with non-negligible probability the output of a PRF from the output of a truly random function. Therefore, no such adversary can exist.
This reasoning assumes that the IV is never reused, but since the IV is supposed to be chosen uniformly at random, this *can* happen. So we need to show that this happens with only negligible probability.
Indeed, the adversary Eve makes $q$ queries which means $q$ messages with $q$ IV's. Each IV is chosen uniformly from $\{0,1\}^{\frac{3}{4}l_b}$, so the probability that an IV is repeated is $\frac{q^2}{2^{\frac{3}{4}l_b + 1}}$ which is negligible, since Eve must be efficient and therefore $q$ needs to be polynomial.
If you have two ciphertexts
The first step is to XOR the two ciphertexts
The second and final step is to XOR this result with the known message
This attack clearly illustrates that initialisation vectors should never be repeated.
Even if the IV is chosen uniformly at random, there is still a chance that it is repeated and security is broken. Nevertheless, the number of possible IVs is usually so large that the probability of this actually happening is negligible.